package ljl.codetop;

public class _5_longest_palindrome {

    /**
     * info 印象中，遍历每个字符，然后往两个方向找？
     * info 有个二维数组，记录 i 到 j 是不是回文
     * info 有个结果记录开始和结束，最后返回 substring 开整
     *
     * info 说了这么多，其实不会做，没思路
     *
     * info 看答案吧，放弃了
     */
    static class trytry {
        // abcba
        public String longestPalindrome(String s) {
            int n = s.length();
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                dp[i][i] = 1;
            }
            int l = -1, r = 0, max = 1;
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {

                }
            }
            return null;
        }
    }

    /**
     * 确实难，遍历长度，然后从头开始枚举左边界，算出来右边界，然后看两头的数是不是一样
     * 由于是从小到大遍历的长度，所以只看两头就行了
     * 有个初始情况，就是长度小于 4 时，只要两头的一样就符合条件，这个要单独设置
     * 其它情况，得看之前保存的结果了。
     */
    static class off1 {
        public String longestPalindrome(String s) {
            int len = s.length();
            if (len < 2) return s;
            int max = 1, begin = 0;
            boolean[][] dp = new boolean[len][len];
            for (int i = 0; i < len; i++) dp[i][i] = true;
            char[] charArray = s.toCharArray();
            // l 是长度
            for (int l = 2; l <= len; l++) {
                // 枚举左边界 i
                for (int i = 0; i < len; i++) {
                    // 计算右边界 j
                    int j = l + i - 1;
                    if (j >= len) break;
                    if (charArray[i] != charArray[j]) {
                        dp[i][j] = false;
                        continue;
                    }
                    // 这属于斜着遍历，从中线开始遍历的，而且长度小于 4 的是直接算出来的
                    // 到后面大于 3 了，根据之前的来了，比如 3, 6，长度是 4，要看 4, 5 啥样，这个东西是之前算过的
                    // 这个条件极其关键，如果当前字串长度 1-3，直接设置成 true
                    if (j - i < 3) dp[i][j] = true;
                    // 当前字串长度大于 3，使用递推，从右下角的推断
                    else dp[i][j] = dp[i + 1][j - 1];
                    if (dp[i][j] && j - i + 1 > max) {
                        max = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + max);
        }
    }

    static class copy_off1 {
        public String longestPalindrome(String s) {
            int n = s.length();
            boolean[][] yes = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                yes[i][i] = true;
            }
            int resL = 0, max = 1;
            char[] arr = s.toCharArray();
            for (int i = 2; i <= n; i++) {
                for (int l = 0; l < n; l++) {
                    int r = l + i - 1;
                    if (r >= n) break;
                    if (arr[l] != arr[r]) {
                        yes[l][r] = false;
                        continue;
                    }
                    if (i < 4) yes[l][r] = true;
                    else yes[l][r] = yes[l + 1][r - 1];
                    if (yes[l][r] && i > max) {
                        max = i;
                        resL = l;
                    }
                }
            }
            return s.substring(resL, resL + max);
        }
    }

    static class off2 {
        public String longestPalindrome(String s) {
            if (s == null || s.length() < 1) {
                return "";
            }
            int start = 0, end = 0;
            for (int i = 0; i < s.length(); i++) {
                // 难点 1
                int len1 = expandAroundCenter(s, i, i);
                int len2 = expandAroundCenter(s, i, i + 1);
                int len = Math.max(len1, len2);
                if (len > end - start) {
                    // 难点 2，中点怎么算出来起始点？
                    // 奇数：1 2 3，从 2 也就是下标 [1]，求出来 0：1 - 1（1 怎么来？len / 2）；2：1 + 1（len / 2)
                    // 偶数：1 2 3 4，从 2 [1]，求出来 0，需要 1 - 1（(len - 1) / 2)；3：1 + 2（len / 2）
                    // 光有这两个例子能不能断定这两个公式是对的？不能
                    // 怎么办？不知道
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            return s.substring(start, end + 1);
        }

        // 0 1
        public int expandAroundCenter(String s, int left, int right) {
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                --left;
                ++right;
            }
            return right - left - 1;
        }
    }

    static class copy_off2 {
        public String longestPalindrome(String s) {
            int n = s.length();
            int begin = 0, end = 0;
            for (int i = 0; i < n; i++) {
                int l1 = expand(s, i, i);
                int l2 = expand(s, i, i + 1);
                int l = Math.max(l1, l2);
                if (l > end - begin + 1) {
                    begin = i - (l - 1) / 2;
                    end = i + l / 2;
                }
            }
            return s.substring(begin, end + 1);
        }

        // 返回的是真实长度
        int expand(String s, int i, int j) {
            while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
                i--; j++;
            }
            return j - i - 1;
        }
    }

}
